import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-05-29
 * Time: 11:49
 */
public class TestHeap {

    public int[] elem;
    public int usedSize;

    public TestHeap(){
        this.elem =  new int[10];
    }

    //建堆
    public void creativeHeap(int[] array){
        //将elem初始化元素
        for(int i =0;i<array.length;++i){
            this.elem[i] =  array[i];
            this.usedSize++;
        }
        //建成大堆
        //从最后一个根节点开始向下调整
        for(int root = (this.usedSize-1-1)/2;root>=0;root--){
            shiftDown(root,this.usedSize);//建堆采用向下调整
        }

    }

    //向下调整
    public void shiftDown(int root,int len){
        int parents = root;
        int child = 2*parents+1;
        //什么时候调整结束呢？？
        //当我们调整一棵树的时候与它相关的树可能也需要调整，那我们就需要从根节点一直调整到叶子结点
        //如果发现需要调整的元素下标超过数组的有效范围内，那就证明已经到达叶子结点不在调整
        while(child<len){
            //找到两个孩子中最大的元素，然后与parent交换
            //并且这里要注意不能child+1不能越界
            if(child+1<len&&this.elem[child]<this.elem[child+1]){
                child++;
            }
            //此时child已经是两个孩子中最大的值

            //如果发现孩子中的最大值比parent的值大那就需要交换，
            if(this.elem[parents]<this.elem[child]){
                swap(this.elem,parents,child);
                parents = child;
                child = 2*parents+1;
            }else {
                //否则不进行交换证明已经是大根堆不需要交换跳出循环
                break;
            }
        }
    }

    public void swap(int[] elem,int i,int j){
        int tmp = this.elem[i];
        this.elem[i] = this.elem[j];
        this.elem[j] = tmp;
    }

    private boolean isFull(){
        return this.usedSize==this.elem.length;
    }


    public void shiftUp(int child){
        int parents = (child-1)/2;
        while(child>0){
            if(this.elem[child]>this.elem[parents]){
                //如果孩子节点大于父节点需要进行交换
                swap(this.elem,parents,child);
                child = parents;//孩子改变
                parents = (child-1)/2;//双亲改变
            }else {
                //否则已经是大堆不需要贾环
                break;
            }
        }
    }

    //堆的插入
    public void offer(int val){
         //如果满了就需要增容
        if(isFull()){
            this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[usedSize]= val;
        //此时需要向上调整
        this.usedSize++;
        //对最后一个元素进行向上调整
        shiftUp(this.usedSize-1);
    }

    //判断是否空
    public boolean isEmpty(){
        return this.usedSize==0;
    }

    //堆的删除
    public void poll(){
        if(isEmpty()){
            System.out.println("优先级队列为空不能进行删除操作！！！");
            return;
        }
        //堆的删除就是删除堆顶元素
        //思路就是将堆顶元素与最后一个元素交换,然后删除最后一个元素
        swap(this.elem,0,this.usedSize-1);
        //调整完要对堆顶元素向下调整
        //此时调整到删除元素之后的this.usedSize-1。
        this.usedSize--;
        shiftDown(0,this.usedSize-1);
    }

    public int peek(){
        return this.elem[0];
    }

}
